package main.Q501_600;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Q531_540 {
    public static void main(String[] args) {
        System.out.println("Question531：");
        System.out.println("Question532：");
        System.out.println("Question533：");
        System.out.println("Question534：");
        System.out.println("Question535：TinyURL的加密与解密");
        System.out.println("Question536：");
        System.out.println("Question537：复数乘法");
        System.out.println("Question538：把二叉搜索树转换为累加树");
        System.out.println("Question539：最小时间差");
        System.out.println("Question540：有序数组中的单一元素");
    }
}

class Question535{
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        return longUrl;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return shortUrl;
    }
}

class Question537{
    public static String complexNumberMultiply(String num1, String num2) {
        StringBuffer result=new StringBuffer();
        String[] str1=num1.split("\\+");//需转义
        String[] str2=num2.split("\\+");
        str1[1]=str1[1].substring(0,str1[1].length()-1);
        str2[1]=str2[1].substring(0,str2[1].length()-1);
        String real=String.valueOf(Integer.valueOf(str1[0])*Integer.valueOf(str2[0])-Integer.valueOf(str1[1])*Integer.valueOf(str2[1]));
        String virtual=String.valueOf(Integer.valueOf(str1[0])*Integer.valueOf(str2[1])+Integer.valueOf(str1[1])*Integer.valueOf(str2[0]));
        result.append(real+"+");
        result.append(virtual+"i");
        return result.toString();
    }
}

class Question538{
    public void process(TreeNode root,List<Integer> list,List<Integer> preSum){
        if (root==null) return;
        int index=list.indexOf(root.val),totalSum= preSum.get(preSum.size()-1);
        if (index!=list.size()-1){
            root.val=totalSum-preSum.get(index)+ root.val;
        }
        process(root.left,list,preSum);
        process(root.right,list,preSum);
    }
    public TreeNode convertBST(TreeNode root) {
        TreeNode temp=root;
        List<Integer> list=new ArrayList<>(),preSum=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (temp!=null|| !stack.isEmpty()){
            if (temp!=null){
                stack.push(temp);
                temp=temp.left;
            }else {
                temp=stack.pop();
                list.add(temp.val);
                temp=temp.right;
            }
        }
        int sum=0;
        for (int i=0;i<list.size();i++){
            preSum.add(sum+list.get(i));
            sum+=list.get(i);
        }
        process(root,list,preSum);
        return root;
    }
}

class Question539{
    public int process(String times){
        String[] time=times.split(":");
        int hour=Integer.valueOf(time[0]),minutes=Integer.valueOf(time[1]);
        int totalMinutes=hour*60+minutes;
        return totalMinutes;
    }
    public int findMinDifference(List<String> timePoints) {
        List<Integer> timeList=new ArrayList<>();
        for (String time:timePoints){
            timeList.add(process(time));
        }
        Collections.sort(timeList);
        timeList.add(timeList.get(0)+24*60);
        int result=24*60;
        for (int i=1;i<timeList.size();i++){
            result=Math.min(result,timeList.get(i)-timeList.get(i-1));
        }
        return result;
    }
}

class Question540{
    public static int singleNonDuplicate(int[] nums) {
        int left=0,right= nums.length-1,result=-1;
        if (nums.length==1) return nums[0];
        if (nums[left]!=nums[left+1]) return nums[left];//当单一元素在边界时
        if (nums[right]!=nums[right-1]) return nums[right];
        while (left<right){
            int mid=(left+right)/2;
            int temp=-1;
            if (nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]) {
                result=nums[mid];
                break;
            }else if (nums[mid]==nums[mid-1]) {
                temp=mid-1;
                if ((right-temp)%2==1) right=mid;//该侧为偶数个数
                else left=temp;//该侧为奇数个数，单一元素在内
            }
            else {
                temp=mid+1;
                if ((temp-left)%2==1) left=mid;
                else right=temp;
            }
        }
        return result;
    }
}